package com.jxm.graph;

import com.jxm.linear.Queue;

/**
 * @Author: jxm
 * @Description: 广度优先搜索
 * @Date: 2022/8/1 15:46
 * @Version: 1.0
 */
public class BreadthFirstSearch {

    // 存储顶点 索引代表顶点，值表示当前顶点是否已经被搜索
    private boolean[] marked;
    //记录有多少个顶点与s顶点相通
    private int count;
    //用来存储待搜索邻接表的点
    private Queue<Integer> waitSearch;

    /**
     * 构造广度优先搜索对象，使用广度优先搜索找出G图中s顶
     * 点的所有相邻顶点
     * @param G
     * @param s
     */
    public BreadthFirstSearch(Graph G, int s){
        //初始化marked数组
        this.marked = new boolean[G.V()];
        //初始化跟顶点s相通的顶点数量
        this.count = 0;
        this.waitSearch = new Queue<Integer>();
        dfs(G,s);
    }

    /**
     * 使用深度优先搜索找出G图中v顶点的所有相通顶点
     * @param G
     * @param v
     */
    private void dfs(Graph G, int v){
        //把当前顶点v标记为已经搜索
        marked[v] = true;
        //让顶点v进去队列，待搜索
        waitSearch.enqueue(v);
        //通过循环，如果队列不为空，则从队列中弹出一个待搜索的顶点进行搜索
        while (!waitSearch.isEmpty()){
            //弹出一个待搜索的顶点
            Integer wait = waitSearch.dequeue();

            //遍历wait顶点的邻接表
            for (Integer w : G.adj(wait)) {
                if(!marked(w)){
                    dfs(G,w);
                }
            }
        }

        //让相通的顶点+1
        count++;

    }

    /**
     * 判断w顶点与s顶点是否相通
     * @param w
     * @return
     */
    public boolean marked(int w){
        return marked[w];
    }

    /**
     * 获取与顶点s相通的所有顶点的总数
     * @return
     */
    public int count(){
        return count;
    }
}
